


/**
 * 稀疏集合
 */
export class SparseSet {

    /**
     * 无效值
     */
    invalid: number = 0;
    /**
     * 最大数量
     */
    max_count: number = 0;
    
    private __packed: Uint32Array;
    private __index: number = 0;
    private __sparse: Uint32Array;

    constructor(max_count: number) {
        this.max_count = this.invalid = max_count;
        this.__packed = new Uint32Array(max_count);
        this.__sparse = new Uint32Array(max_count);
        this.__packed.fill(this.invalid);
        this.__sparse.fill(this.invalid);
    }

    /**
     * 添加
     * @param id  (0-max_count)
     */
    add(id: number): void {
        if (id < 0 || id >= this.max_count) {
            throw new Error("id out of range");
        }
        this.__packed[this.__index] = id;
        this.__sparse[id] = this.__index;
        this.__index++;
    }

    /**
     * 是否包含
     * @param id 
     */
    contains(id: number): boolean {
        if (id < 0 || id >= this.max_count) {
            return false;
        }
        if (this.__sparse[id] == this.invalid) {
            return false;
        }
        return true;
    }

    /**
     * 删除
     * @param id 
     */
    remove(id: number): void {
        if (id < 0 || id >= this.max_count) {
            throw new Error("id out of range");
        }
        let del_pack_index = this.__sparse[id];
        let last_idx = this.__index - 1;
        if (this.length == 1 || del_pack_index == last_idx) {
            this.__packed[last_idx] = this.invalid;
            this.__sparse[id] = this.invalid;
        } else {
            let swap_id = this.__packed[last_idx];
            this.__packed[del_pack_index] = swap_id;
            this.__sparse[id] = this.invalid;
            this.__sparse[swap_id] = del_pack_index;
            this.__packed[last_idx] = this.invalid;
        }
        this.__index--;
    }

    /**
     * 清除
     */
    clear(): void {
        this.__packed.fill(this.invalid);
        this.__sparse.fill(this.invalid);
        this.__index = 0;
    }

    destory(): void {
        this.max_count = 0;
        this.__index = 0;
        this.__packed = null;
        this.__sparse = null;
    }

    /**
     * 获取packed索引
     * @param id 
     * @returns 
     */
    getPackIdx(id: number): number {
        if (id < 0 || id >= this.max_count) {
            throw new Error("id out of range");
        }
        return this.__sparse[id];
    }

    /**
     * 最后一个元素
     */
    get end(): number {
        return this.__packed[this.__index - 1];
    }

    /**
     * 长度
     */
    get length(): number {
        return this.__index;
    }
}